package tree;

import java.util.LinkedList;
import java.util.Queue;

import utils.CreateUtils;

public class LevelByLevelTraversal {

	public static <T extends Comparable<? super T>> void traverseByLevel(Node<T> root) {
		if (root == null)
			return;
		
		Queue<Node<T>> q = new LinkedList<Node<T>>();
		q.add(root);
		q.add(null);
		while (!q.isEmpty()) {
			Node<T> node = q.poll();
			if (node != null) {
				System.out.printf("%s ", node.value.toString());
				if (node.left != null)
					q.add(node.left);
				if (node.right != null)
					q.add(node.right);
			}
			else {
				System.out.println();
				if (!q.isEmpty())
					q.add(null);
			}
		}
	}
	
	public static void traverseByLevel1(Node<Integer> root) {
		if (null == root)
			return;
		int currLevel = 1;
		int nextLevel = 0;
		Queue<Node<Integer>> q = new LinkedList<Node<Integer>>();
		q.add(root);
		while (!q.isEmpty()) {
			Node<Integer> node = q.poll();
			--currLevel;
			if (node != null) {
				System.out.printf("%s ", node.value.toString());
				q.add(node.left);
				q.add(node.right);
				nextLevel += 2;
			}
			if (currLevel == 0) {
				System.out.println();
				currLevel = nextLevel;
				nextLevel = 0;
			}
		}
	}
	
	public static void traverseByLevel2(Node<Integer> root) {
		if (root == null)
			return;
		Queue<Node<Integer>> q = new LinkedList<Node<Integer>>();
		q.add(root);
		int currLevel = 1;
		int nextLevel = 0;
		while (!q.isEmpty()) {
			Node<Integer> n = q.poll();
			if (n.left != null) {
				q.add(n.left);
				nextLevel++;
			}
			if (n.right != null) {
				q.add(n.right);
				nextLevel++;
			}
			System.out.print(n.value + " ");
			currLevel--;
			if (currLevel == 0) {
				System.out.println();
				currLevel = nextLevel;
				nextLevel = 0;
			}
		}
	}

	public static void main(String[] args) {
		traverseByLevel(CreateUtils.bstWithTenNodes());
	}

}
